#include <stdio.h>
#include <stdlib.h>

/* 顺序栈及其操作 */
typedef enum {false, true} bool;
typedef int SElemSet;
#define NIL -1

typedef int Position; /* 整型下标，表示元素的位置 */
typedef struct StackNode *Stack;
struct StackNode {
    int capacity; /* 顺序栈的容量 */
    Position top; /* 顺序栈的栈顶指针，初始化为-1 */
    SElemSet *data; /* 存储数据的数组 */
};

void InitStack(Stack stack, int kMaxSize);
bool IsFull(Stack stack);
bool IsEmpty(Stack stack);
void Push(Stack stack, SElemSet x);
SElemSet Top(Stack stack);
void Pop(Stack stack);
void DestroyStack(Stack stack);
/* 顺序栈及其操作 结束 */

#define ErrorCode 1e9 /* 错误代码 */
#define kMaxLen 1000 /* 表达式字符串的最大长度为kMaxLen-1 */
/* 枚举值对应加、减、乘、除、取模、操作数、结束标志 */
typedef enum { plus, minus, times, divide, mod, operand, EndCode } TokenType;

int Length(char s[]);
TokenType GetToken(char s[], Position *p, SElemSet *num);
SElemSet Calculate(SElemSet op1, TokenType token, SElemSet op2);
SElemSet PostFixEval(char expr[]);

int main(void) {
    char expr[kMaxLen];
    Position i;

    /* 读入表达式 */
    i = 0;
    expr[i] = getchar();
    while (expr[i] != '\n') {
        i++;
        expr[i] = getchar();
    }
    expr[i] = '\0';
    /* 输出表达式的值 */
    printf("%d\n", PostFixEval(expr));

    return 0;
}

void InitStack(Stack stack, int kMaxSize) {
    /* 初始化一个大小为kMaxSize的顺序栈 */
    stack->capacity = kMaxSize;
    stack->top = -1;
    stack->data = (SElemSet *)malloc(sizeof(SElemSet) * kMaxSize);
}

bool IsFull(Stack stack) {
    /* 判断栈是否已满 */
    if ((stack->top + 1) == stack->capacity)
        return true;
    else
        return false;
}

bool IsEmpty(Stack stack) {
    /* 判断栈是否为空 */
    if (stack->top == -1)
        return true;
    else
        return false;
}

void Push(Stack stack, SElemSet x) {
    if (IsFull(stack)) {
        /*printf("错误：栈已满。\n");*/
    } else {
        stack->top++;
        stack->data[stack->top] = x;
    }
}

SElemSet Top(Stack stack) {
    if (IsEmpty(stack)) {
        /*printf("错误：栈为空。\n");*/
        return NIL;
    } else {
        return stack->data[stack->top];
    }
}

void Pop(Stack stack) {
    if (IsEmpty(stack)) {
        /*printf("错误：栈为空。\n");*/
    } else {
        stack->top--;
    }
}

void DestroyStack(Stack stack) {
    free(stack->data);
    free(stack);
}

int Length(char s[]) {
    /* 求字符数组s的长度 */
    int len = 0;
    while (s[len] != '\0')
        len++;
    return len;
}

TokenType GetToken(char s[], Position *p, SElemSet *num) {
    /* 从s[p]开始，获取一个元素，返回其类型 */
    /* 并更新p到下一个元素的起始位置 */
    /* 若元素是操作数，则将其值存在num */
    TokenType ret;
    Position i;

    i = (*p);
    switch (s[i]) {
    case '+':
        ret = plus;
        break;
    case '-':
        ret = minus;
        break;
    case '*':
        ret = times;
        break;
    case '/':
        ret = divide;
        break;
    case '%':
        ret = mod;
        break;
    case '\0':
        ret = EndCode;
        break;
    default: { /* 处理操作数 */
        ret = operand;
        (*num) = 0;
        while (s[i] >= '0' && s[i] <= '9') {
            (*num) = (*num) * 10 + (s[i] - '0');
            i++;
        }
        i--; /* i指向当前元素末尾 */
        break;
    }
    }
    i++; /* i指向当前元素的下一个位置 */
    while (s[i] == ' ')
        i++; /* 跳过空格 */
    /* i指向下一个元素的开头 */
    (*p) = i;
    return ret;
}

SElemSet Calculate(SElemSet op1, TokenType token, SElemSet op2) {
    SElemSet ret;

    switch (token) { /* 根据token类型进行计算 */
    case plus:
        ret = op1 + op2;
        break;
    case minus:
        ret = op1 - op2;
        break;
    case times:
        ret = op1 * op2;
        break;
    case divide: {
        if (op2 == 0) {
            printf("错误：除法操作分母为零。\n");
            ret = ErrorCode;
        } else {
            ret = op1 / op2;
        }
        break;
    }
    case mod: {
        if (op2 == 0) {
            printf("错误：取模操作除数为零。\n");
            ret = ErrorCode;
        } else {
            ret = op1 % op2;
        }
        break;
    }
    default:
        break;
    }
    return ret;
}

/* 算法3-13：后缀表达式求值  PostFixEval(expr) */
SElemSet PostFixEval(char expr[]) {
    /* 后缀表达式expr存储为字符数组，操作数与操作符之间以1个空格分隔 */
    /* 注意：这里仅处理非负操作数 */
    TokenType token; /* 记录表达式中一个元素的类型 */
    Position p; /* 表达式当前开始获取元素的位置 */
    SElemSet num, operand1, operand2, result;
    Stack stack;

    stack = (Stack)malloc(sizeof(struct StackNode));
    InitStack(stack, Length(
                  expr)); /* 创建顺序栈，容量等于表达式长度 */
    p = 0; /* 从表达式头开始 */
    token = GetToken(expr, &p, &num); /* 从表达式中取出一个元素 */
    while (token != EndCode) {
        if (token == operand) { /* 若是操作数 */
            Push(stack, num); /* 则将操作数的值入栈 */
        } else {
            operand2 = Top(stack);
            Pop(stack);
            operand1 = Top(stack);
            Pop(stack);
            if (operand1 == NIL || operand2 == NIL) {
                printf("错误：表达式不规范。\n");
                result = ErrorCode;
                break;
            } else {
                result = Calculate(operand1, token, operand2); /* 计算 */
                Push(stack, result); /* 计算结果入栈 */
            }
        }
        token = GetToken(expr, &p, &num); /* 从表达式中取出下一个元素 */
    }
    if (result != ErrorCode) {
        result = Top(stack);
        Pop(stack);
        if (IsEmpty(stack) == false) {
            printf("错误：表达式不规范。\n");
            result = ErrorCode;
        }
    }
    DestroyStack(stack);
    return result;
}
/* 算法3-13 结束 */